"""
NC34 不同路径的数目(一)
https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=117&&tqId=37736&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param m int整型
# @param n int整型
# @return int整型
#


class Solution:
    memo = {}

    def method1(self, m: int, n: int) -> int:
        """
        递归+记忆化搜索
        """

        if m == 1 or n == 1:
            return 1

        if (m, n) not in self.memo:
            res = self.method1(m-1, n) + self.method1(m, n-1)
            self.memo[(m, n)] = res

        return self.memo[(m, n)]

    def method2(self, m: int, n: int) -> int:
        """
        动态规划
        """
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if i == 1 or j == 1:
                    # 只有1行或1列，只有1条路
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m][n]

    def uniquePaths(self, m: int, n: int) -> int:
        """
        数据范围：0<n,m≤100，保证计算结果在32位整型范围内
        """
        return self.method2(m, n)


def test():
    obj = Solution()
    m, n = 2, 2
    res = obj.uniquePaths(m, n)
    print(res)


if __name__ == "__main__":
    test()
